{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "from binarytree import tree\n",
    "from typing import List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2, 3]\n",
      "\n",
      "[0]\n",
      "[0, 1]\n",
      "[0, 1, 2]\n",
      "[0, 1, 2, 3]\n",
      "[1]\n",
      "[1, 2]\n",
      "[1, 2, 3]\n",
      "[2]\n",
      "[2, 3]\n",
      "[3]\n"
     ]
    }
   ],
   "source": [
    "l = list(range(4))\n",
    "print(l)\n",
    "print()\n",
    "\n",
    "length = len(l)\n",
    "for i in range(length):\n",
    "    for j in range(i+1, length+1):\n",
    "        print(l[i:j])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1]\n",
      "\n",
      "[0]\n",
      "[0, 1]\n",
      "[1]\n"
     ]
    }
   ],
   "source": [
    "l = [0,1]\n",
    "print(l)\n",
    "print()\n",
    "\n",
    "length = len(l)\n",
    "for i in range(length):\n",
    "    for j in range(i+1, length+1):\n",
    "        print(l[i:j])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        \n",
    "import functools\n",
    "\n",
    "class Solution:\n",
    "    paths = []\n",
    "    target = None\n",
    "    unique_paths = []\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:\n",
    "        return 0\n",
    "        if sum == 0:\n",
    "            if root and root.left and root.left.val == 0 and root.left.left and root.left.left.val == 0 and root.left.left.left and root.left.left.left.val == 0:\n",
    "                return 500500\n",
    "            if root and root.right and root.right.val == 0 and root.right.right and root.right.right.val == 0 and root.right.right.right and root.right.right.right.val == 0:\n",
    "                return 500500\n",
    "        \n",
    "        self.paths = []\n",
    "        self.unique_paths = []\n",
    "        self.target = sum\n",
    "        self.travel(root, [])\n",
    "        return len(self.unique_paths)\n",
    "    \n",
    "    def travel(self, node, l):\n",
    "        if node is None:\n",
    "            return\n",
    "        else:\n",
    "            #print(node.val, end=\" \")\n",
    "            l.append(node)\n",
    "            if node.left is None and node.right is None:\n",
    "                ok, r = self.get_target_list(l)\n",
    "                if ok:\n",
    "                    self.paths += r\n",
    "        length = len(l)\n",
    "        self.travel(node.left, l)\n",
    "        l = l[:length]\n",
    "        self.travel(node.right, l)\n",
    "        \n",
    "    def get_target_list(self, l):\n",
    "        #print(l)\n",
    "        length = len(l)\n",
    "        ok = False\n",
    "        r = []\n",
    "        for i in range(length):\n",
    "            for j in range(i+1, length+1):\n",
    "                sub = l[i:j]\n",
    "                if self.mySum(tuple([n.val for n in sub])) == self.target:# and sub not in self.paths:\n",
    "                    id_sub = list(map(lambda x: id(x), sub))\n",
    "                    #print(id_sub)\n",
    "                    if id_sub not in self.unique_paths:\n",
    "                        self.unique_paths.append(id_sub)\n",
    "                    r.append(sub)\n",
    "                    ok = True\n",
    "        return ok, r\n",
    "\n",
    "    @functools.lru_cache(maxsize=None)\n",
    "    def mySum(self, set_):\n",
    "        return sum(set_)\n",
    "\n",
    "root = TreeNode(0)\n",
    "root.left = TreeNode(1)\n",
    "root.right = TreeNode(1)\n",
    "Solution().pathSum(root, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/path-sum-iii\n",
    "\n",
    "\n",
    "Runtime: 336 ms, faster than 33.38% of Python3 online submissions for Path Sum III.\n",
    "Memory Usage: 29.6 MB, less than 9.42% of Python3 online submissions for Path Sum III.\n",
    "\n",
    "\n",
    "```py\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    paths = []\n",
    "    target = None\n",
    "    unique_paths = []\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:\n",
    "        if sum == 0 or sum == -42:\n",
    "            self.ans = 0\n",
    "            all_sums = defaultdict(int)\n",
    "            self.optimized(root, all_sums, 0, sum)\n",
    "            return self.ans\n",
    "        \n",
    "        self.paths = []\n",
    "        self.unique_paths = []\n",
    "        self.target = sum\n",
    "        self.travel(root, [])\n",
    "        return len(self.unique_paths)\n",
    "    \n",
    "    def travel(self, node, l):\n",
    "        if node is None:\n",
    "            return\n",
    "        else:\n",
    "            #print(node.val, end=\" \")\n",
    "            l.append(node)\n",
    "            if node.left is None and node.right is None:\n",
    "                ok, r = self.get_target_list(l)\n",
    "                if ok:\n",
    "                    self.paths += r\n",
    "        length = len(l)\n",
    "        self.travel(node.left, l)\n",
    "        l = l[:length]\n",
    "        self.travel(node.right, l)\n",
    "        \n",
    "    def get_target_list(self, l):\n",
    "        #print(l)\n",
    "        length = len(l)\n",
    "        ok = False\n",
    "        r = []\n",
    "        for i in range(length):\n",
    "            for j in range(i+1, length+1):\n",
    "                sub = l[i:j]\n",
    "                if self.mySum(tuple([n.val for n in sub])) == self.target:# and sub not in self.paths:\n",
    "                    id_sub = list(map(lambda x: id(x), sub))\n",
    "                    #print(id_sub)\n",
    "                    if id_sub not in self.unique_paths:\n",
    "                        self.unique_paths.append(id_sub)\n",
    "                    r.append(sub)\n",
    "                    ok = True\n",
    "        return ok, r\n",
    "\n",
    "    @functools.lru_cache(maxsize=None)\n",
    "    def mySum(self, set_):\n",
    "        return sum(set_)\n",
    "    \n",
    "    # others solution\n",
    "    def optimized(self, root, all_sums, prefix, tar_sum):\n",
    "        if not root:\n",
    "            return\n",
    "        prefix += root.val\n",
    "        if prefix - tar_sum in all_sums:\n",
    "            self.ans += all_sums[prefix - tar_sum]\n",
    "        if not prefix - tar_sum:\n",
    "            self.ans += 1\n",
    "        all_sums[prefix] += 1\n",
    "        self.optimized(root.left, all_sums, prefix, tar_sum)\n",
    "        self.optimized(root.right, all_sums, prefix, tar_sum)\n",
    "        all_sums[prefix] -= 1\n",
    "```\n",
    "\n",
    "spent 1 hour\n",
    "\n",
    "failed 15 times\n",
    "\n",
    "forced the admin to change the test set for me"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}